//<p>给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。</p>
//
//<p><a href="https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin" target="_blank">百度百科</a>中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（<strong>一个节点也可以是它自己的祖先</strong>）。”</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p> 
//<img alt="" src="https://assets.leetcode.com/uploads/2018/12/14/binarytree.png" style="width: 200px; height: 190px;" /> 
//<pre>
//<strong>输入：</strong>root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
//<strong>输出：</strong>3
//<strong>解释：</strong>节点 <span><code>5 </code></span>和节点 <span><code>1 </code></span>的最近公共祖先是节点 <span><code>3 。</code></span>
//</pre>
//
//<p><strong>示例 2：</strong></p> 
//<img alt="" src="https://assets.leetcode.com/uploads/2018/12/14/binarytree.png" style="width: 200px; height: 190px;" /> 
//<pre>
//<strong>输入：</strong>root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
//<strong>输出：</strong>5
//<strong>解释：</strong>节点 <span><code>5 </code></span>和节点 <span><code>4 </code></span>的最近公共祖先是节点 <span><code>5 。</code></span>因为根据定义最近公共祖先节点可以为节点本身。
//</pre>
//
//<p><strong>示例 3：</strong></p>
//
//<pre>
//<strong>输入：</strong>root = [1,2], p = 1, q = 2
//<strong>输出：</strong>1
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul> 
// <li>树中节点数目在范围 <code>[2, 10<sup>5</sup>]</code> 内。</li> 
// <li><code>-10<sup>9</sup> &lt;= Node.val &lt;= 10<sup>9</sup></code></li> 
// <li>所有 <code>Node.val</code> <code>互不相同</code> 。</li> 
// <li><code>p != q</code></li> 
// <li><code>p</code> 和 <code>q</code> 均存在于给定的二叉树中。</li> 
//</ul>
//
//<div><div>Related Topics</div><div><li>树</li><li>深度优先搜索</li><li>二叉树</li></div></div><br><div><li>👍 1908</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

import com.rising.leetcode.editor.cn.doc.object.ListNode;
import com.rising.leetcode.editor.cn.doc.object.TreeNode;

import java.util.LinkedList;
import java.util.List;

/**
 * 二叉树的最近公共祖先
 * @author DY Rising
 * @date 2022-08-17 20:20:00
 */
public class P236_LowestCommonAncestorOfABinaryTree{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P236_LowestCommonAncestorOfABinaryTree().new Solution();
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<Integer> alist = new LinkedList();
        List<Integer> blist = new LinkedList();
        List<Integer> alistTemp = new LinkedList();
        List<Integer> blistTemp = new LinkedList();
        findParent(root, p.val, alistTemp);
        findParent(root, q.val, blistTemp);
        for (int i = 0; i < alistTemp.size(); i++) {
            alist.add(0, alistTemp.get(i));
        }
        for (int i = 0; i < blistTemp.size(); i++) {
            blist.add(0, blistTemp.get(i));
        }

        int length = alist.size() > blist.size() ? blist.size() : alist.size();
        int sum = 0;
        for (int i = 0; i < length; i++) {
            if (!alist.get(i).equals(blist.get(i))) {
                int elemet = (int) alist.get(i - 1);
                return new TreeNode(elemet);
            }
            sum++;
        }
        if (sum == length) {
            return new TreeNode(alist.get(length - 1));
        }
        return null;
    }

    /**
     * 找到某一个节点的父路径
     * @param node
     * @param element
     * @param list
     * @return
     */
    public TreeNode findParent(TreeNode node,int element, List<Integer> list) {
        if (node == null) {
            return node;
        }
        if (node.val == element) {
            list.add(node.val);
            return node;
        }

        TreeNode left = findParent(node.left, element, list);
        TreeNode right = findParent(node.right, element, list);
        if (left != null) {
            list.add(node.val);
            return left;
        }
        if (right != null) {
            list.add(node.val);
            return right;
        }
        return null;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
